1. Technical Field
The present invention relates, in general, to an improved method and system to be utilized with wireless communication systems having cellular architectures. In particular, the present invention relates to an improved method and system, to be utilized with wireless communication systems having cellular architectures, and which assigns groups of channels to individual cells within the system in such a fashion that system-wide signal to noise ratio is maximized over some defined geographical area.
2. Description of the Related Art
The present invention is related to wireless communication systems, and, in particular, to wireless communication systems having a cellular architecture (e.g., cellular telephony, Personal Communication Systems, or Global System for Mobil Communication). Wireless communication refers to the fact that transmission between sending and receiving stations occurs via electromagnetic radiation not guided by any hard physical path (e.g., by microwave link.) Cellular architecture refers to the fact that the wireless system effects service over an area by utilizing a system that can be pictographically represented as a cellular grid.
Wireless cellular communication is the latest incarnation of a technology that was originally known as mobile telephone systems. Early mobile telephone system architecture was structured similar to television broadcasting. That is, one very powerful transmitter located at the highest spot in an area would broadcast in a very large radius. If a user were in the useable radius, then that user could broadcast to the base station and communicate by radiotelephone to the base station. However, such systems proved to be very expensive for the users and not very profitable to the communication companies supplying such services. The primary limiting factor of the original mobile telephone systems was that the number of channels available for use was limited due to severe channel-to-channel interference within the area served by the powerful transmitter. Thus, a problem arose as to how to provide more channels within the service area.
Counterintuitively, engineers discovered that channel-to-channel interference effects within the service area were not due solely to the distance between stations communicating with the base transmitter (which intuitively would seem to give rise to the interference,) but were also inversely related to the transmitter power (radius) of the area being served by the transmitter. Engineers found that by reducing the radius of an area by fifty percent, service providers could increase the number of potential customers in an area fourfold. It was found that systems based on areas with a one-kilometer radius would have one hundred times more channels than systems with areas with a ten-kilometers in radius. Speculation led to the conclusion that by reducing the radius of areas to a few hundred meters, the number of calls that could be served by each cell could be greatly increased.
Thus, reducing the power of the central transmitter allowed a significant increase in the number of available channels by reducing channel-to-channel interference within an area. However, as the power of the central transmitter was reduced, the serviceable area was also reduced. Thus, although reducing transmission power increased the number of available channels, the small service area provided by such reduced power did not make such radio telephone systems attractive communication options for many users. Thus, a problem arose relating to how to utilize the discovery that smaller cell sizes increased available channels in a fashion that would provide service attractive to users.
This problem was solved by the invention of the wireless cellular architecture concept. The wireless cellular architecture concept utilizes geographical subunits called "cells" and is buttressed by what is known as a frequency reuse concept. A cell is the basic geographic unit of a cellular system. Cells are base stations (a base station consists of hardware located at the defining location of a cell and includes power sources, interface equipment, radio frequency transmitters and receivers, and antenna systems) transmitting over small geographic areas that are represented as hexagons. Each cell size varies depending on the landscape. The term "cellular" comes from the honeycomb shape of the areas into which a coverage region is divided. Because of constraints imposed by natural terrain and man-made structures, the true shape of cells is not a perfect hexagon, but such shape serves as an effective tool for design engineering.
Within each cell a base station controller talks to many mobile subscriber units at once, utilizing one defined transmit/receive communications channel per mobile subscriber unit. A mobile subscriber unit (a control unit and a transceiver that transmits and receives wireless transmissions to and from a cell site) uses a separate, temporary wireless channel to talk to a cell site. Transmit/receive communication channels utilize a pair of frequencies for communication--one for transmitting from the cell site base station controller, named the forward link, and one frequency for the cell site to receive calls from the users, named the reverse link. Both the forward and reverse link must have sufficient bandwidth to allow transmission of user data.
The frequency reuse concept is what made wireless cellular communications a viable reality. Wireless communication is regulated by government bodies (e.g., the Federal Communications Commission.) Government bodies dictate what frequencies in the wireless spectrum can be utilized for particular applications. Consequently, there is a finite set of frequencies available for use with cellular communications. The frequency reuse concept is based on assigning to each cell a group of radio channels used within a small geographic area (cell). Adjacent cells are assigned a group of channels that is completely different from any neighboring cell. Thus, in the frequency reuse concept there are always buffer cells between two cells utilizing the same set of frequencies. The cells are sized such that it is not likely that two cells utilizing the same set of frequencies will interfere with each other. Thus, such a scheme allows "frequency reuse" by non-adjacent cells.
Since each contiguous cell utilizes different frequencies, the ability for such a system to supply continuous service across a cell grid requires that a call-in-progress be switched to a new transmit/receive channel as a user transits from one cell into another. That is, since adjacent areas do not use the same wireless channels, a call must either be dropped or transferred from one wireless channel to another when a user crosses the line between adjacent cells. Because dropping the call is unacceptable, the process of "handoff" was created. Handoff occurs when the mobile telephone network automatically transfers a call from wireless channel to wireless channel as a mobile subscriber unit crosses adjacent cells.
Handoff works as follows. During a call, a moving mobile subscriber unit is utilizing one voice channel. When the mobile unit moves out of the coverage area of a given cell site, the reception becomes weak. At this point, the base station controller in use requests a handoff. The system switches the call to another different frequency channel in a new cell without interrupting the call or alerting the user. The call continues as long as the user is talking, and generally the user barely notices the handoff.
The foregoing ideas of cells, frequency reuse, and handoff constituted the invention of the cellular concept. The invention of the cellular concept made the idea of wireless cellular communications a viable commercial reality.
As noted previously, the frequency reuse concept requires assigning groups of cells different groups of frequencies. In practice, in order to do the assignment engineers first assume an ideal hexagon layout of the network and apply an ideal frequency assignment pattern "as if" the distribution of the electromagnetic energy being transmitted to achieve communication perfectly matched the hexagonal shapes.
The frequency assignment method is typically done on some variation of a graph coloring approach. In this approach, the assignment problem is formulated as a graph coloring problem where groups of channels are assigned colors and consequently each hexagon is colored such that no hexagons of the same color touch, which is a way to assure that a "buffer zone" exists between any two cells utilizing the same group of channels. In addition, there have been attempts to train neural networks to mimic what human engineers do by experience and intuition.
FIG. 1 illustrates how the frequency assignment problem is typically solved. In FIG. 1 there is depicted a cell cluster within a wireless communication system having a cellular architecture within which the method and system of the present invention may be implemented. Recall that in the above discussion it was noted that frequency reuse is a concept that has been utilized to allow cellular communications over a large area. It is common to create a cell cluster composed of idealized hexagonal cells, as is shown in FIG. 1, whereby the frequency reuse concept is implemented. A cell cluster is a group of cells. Typically, no channels are reused within a cluster. FIG. 1 illustrates seven-cell cluster 100.
A "cell" is the basic geographic unit of a cellular system. The term "cellular" comes from the honeycomb shape of the areas into which a coverage region is divided. In FIG. 1 each cell 101, 102, 103, 104, 105, 106, and 107 is depicted as a honeycomb shape within which base stations 111, 112, 113, 114, 115, 116 and 117, respectively, are shown. Cells are pictographic representations of the effective geographic area of base station (a base station includes but is not limited to transmitters and receivers sufficient to service existing cell channels within a particular cell) transmitters that are for convenience represented as hexagons. Each cell size varies depending on the landscape. Because of constraints imposed by natural terrain and man-made structures, the true shape of cells is not a perfect hexagon.
Since seven-cell cluster 100 utilizes the frequency reuse concept, each cell in FIG. 1 utilizes a set of channels wherein each channel is based upon a set of carrier frequencies different from those utilized by any other cell 101, 102, 103, 104, 105, 106, 107 within seven-cell cluster 100. Thus, if available frequencies are divided evenly, each cell 101, 102, 103, 104, 105, 106, and 107 will utilize 1/7 of frequencies available for utilization.
Unfortunately, the electromagnetic energy very rarely matches the perfectly arranged hexagonal shapes shown. Variations in terrain and buildings often disrupt the transmitted electromagnetic energy. Consequently, after such a hexagonal has been laid out and groups of frequencies assigned, it is generally found that both the hexagonal model and the frequency assignment are grossly inadequate. Thus, subsequent to the hexagonal modeling and subsequent group of channels assignment, it is typical that a long period of "trial and error" is engaged in where engineers actually go out and empirically determine the true distribution of the individual cells (which often are radically different in shape than the idealized hexagons). FIG. 2 gives a pictorial hypothetical representation of how the idealized hexagons of FIG. 1 might ultimately be "adjusted" to become "real world" cells 201, 202, 203, 204, 205, 206, and 207. Then, after the shape has been adequately determined, the engineers measure the interference in the cells utilizing different channel group assignments and subsequently assign groups of channels based upon the empirical data.
In sum, then, it can be said that generally the frequency assignment problem is typically solved via six steps: (1) an idealized hexagonal distribution of electromagnetic energy within cells is assumed; (2) frequency assignment is done, utilizing any one of a number of approaches, based on the assumed idealized hexagonal distribution; (3) the frequency assignment based on the idealized distribution is implemented in true, physical equipment; (4) physical measurements are taken regarding the true, physical, shape of the cell and physical measurements are taken regarding the true interference measured within each cell; (5) the frequency assignment is adjusted based upon the physical measurements; and (6) thereafter, steps (4) and (5) are iteratively engaged in until engineers determine that satisfactory system performance is achieved.
Deficiencies exist in the typical solutions to the frequency assignment problem in that the re-engineering (i.e., "trial and error") involved in modifying the idealized solution to the frequency assignment problem such that it works in an actual physical system is generally very labor intensive and time consuming. Furthermore, in general, the more diverse the terrain and surrounding building structures are, the more labor intensive the re-engineering effort, in that such diversity often makes the true cells radically different from the assumed perfectly hexagonal shape.
In light of the foregoing, it is apparent that a need exists for a method and system which will provide a solution to the frequency assignment problem which is much more correspondent to real world systems, and thus greatly decrease or eliminate the amount of re-engineering effort required to implement such a solution in true, physical systems.